package seqlist.link;

import seqlist.SeqList;

/**
 * @author yuisama
 * @date 2023/03/19 15:51
 * 双线链表的实现
 **/
public class DoubleLinkedList<E> implements SeqList<E> {
    private int size; // 有效节点个数
    private DoubleNode head; // 头节点
    private DoubleNode tail; // 尾结点

    private class DoubleNode{
        DoubleNode prev;
        E val;
        DoubleNode next;
        public DoubleNode(E val) {
            this.val = val;
        }
        public DoubleNode(DoubleNode prev, E val, DoubleNode next) {
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }

    @Override
    public void add(E element) {
        DoubleNode node = new DoubleNode(element);
        size ++;
        if (head == null) {
            head = node;
        }else {
            node.prev = tail;
            tail.next = node;
        }
        tail = node;
    }

    public void addFirst(E element) {
        DoubleNode node = new DoubleNode(element);
        size ++;
        if (tail == null) {
            tail = node;
        }else {
            node.next = head;
            head.prev = node;
        }
        head = node;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (DoubleNode x = head;x != null;x = x.next) {
            sb.append(x.val).append("->");
            if (x == tail) {
                sb.append("NULL\n");
            }
        }
        return sb.toString();
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index illegal!");
        }
        if (index == 0) {
            addFirst(element);
            return;
        }
        if (index == size) {
            add(element);
            return;
        }
        DoubleNode prev = node(index - 1);
        DoubleNode next = prev.next;
        DoubleNode node = new DoubleNode(prev,element,next);
        // 先处理左边区域
//        node.prev = prev;
        prev.next = node;
        // 再处理右半区域
//        node.next = next;
        next.prev = node;
        size ++;
    }
    // 根据传入索引与中间位置的关系，决定到底从前向后寻找节点还是从后向前寻找节点
    // 内部使用的工具方法
    private DoubleNode node(int index) {
        DoubleNode result = null;
        if (index < (size >> 1)) {
            result = head;
            for (int i = 0; i < index; i++) {
                result = result.next;
            }
        }else {
            result = tail;
            for (int i = size - 1; i > index; i--) {
                result = result.prev;
            }
        }

        return result;
    }

    @Override
    public E removeByIndex(int index) {
        if (!rangeCheck(index)) {
            throw new IllegalArgumentException("remove index illegal!");
        }
        DoubleNode node = node(index);
        unlink(node);
        return node.val;
    }

    @Override
    public void removeByValue(E element) {
        DoubleNode node = head;
        for (int i = 0; i < size; i++) {
            if (node.val.equals(element)) {
                unlink(node);
                return;
            }
            node = node.next;
        }
    }

    @Override
    public void removeAllValue(E element) {
        DoubleNode node = head;
        // 因为每次unlink之后都会修改size的值，但是删除所有元素，
        // 要把所有链表节点全部遍历一遍
        int length = this.size;
        for (int i = 0; i < length; i++) {
            DoubleNode next = node.next;
            if (node.val.equals(element)) {
                unlink(node);
            }
            node = next;
        }
    }
    // 在当前双向链表中删除node节点
    private void unlink(DoubleNode node) {
        DoubleNode prev = node.prev;
        DoubleNode next = node.next;
        // 先处理左半区域
        if (prev == null) {
            this.head = next;
        }else {
            node.prev = null;
            prev.next = next;
        }
        // 在处理右半区域
        if (next == null) {
            this.tail = prev;
        }else {
            node.next = null;
            next.prev = prev;
        }
        size --;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public E get(int index) {
        if (!rangeCheck(index)) {
            throw new IllegalArgumentException("get index illegal!");
        }
        return node(index).val;
    }

    private boolean rangeCheck(int index) {
        if (index < 0 ||index >= size) {
            return false;
        }
        return true;
    }

    @Override
    public boolean contains(E element) {
        return false;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }
}